package leetcode101.tree;

/**
 * @author Synhard
 * @version 1.0
 * @class Code15
 * @description 572. 另一个树的子树
 * 给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。
 * s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
 *
 * 示例 1:
 * 给定的树 s:
 *
 *      3
 *     / \
 *    4   5
 *   / \
 *  1   2
 * 给定的树 t：
 *
 *    4 
 *   / \
 *  1   2
 * 返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
 *
 * 示例 2:
 * 给定的树 s：
 *
 *      3
 *     / \
 *    4   5
 *   / \
 *  1   2
 *     /
 *    0
 * 给定的树 t：
 *
 *    4
 *   / \
 *  1   2
 * 返回 false。
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-06-25 7:58
 */
public class Code15 {

    public static void main(String[] args) {

    }

    public static boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return dfs(root, subRoot);
    }

    private static boolean dfs(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return false;
        }
        if ((root1.val == root2.val) && check(root1, root2)) {
            return true;
        } else {
            return dfs(root1.left, root2) || dfs(root1.right, root2);
        }
    }

    private static boolean check(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        }
        if (root1 != null && root2 != null) {
            if (root1.val == root2.val) {
                return check(root1.left, root2.left) && check(root1.right, root2.right);
            }
        }
        return false;
    }

}
